Software testing ensures that software has been implemented correctly and performs as intended. Testing new versions of previously tested software helps to ensure that any newly added or revised code has not adversely effected any previously working features.
An important goal of software testing is to expose software defects prior to releasing the software. Defect detection and correction is more costly to fix after the software has been released. Therefore, it is desirable to detect and correct defects before the software is released for customer use. Early defect detection saves time and resources and improves customer relations.
Testing of software occurs continuously throughout the software development process. For example, developers may run some preliminary tests to determine whether new or modified code will prevent the software from being built (compiled and linked). Such tests may involve compiling the code to determine whether any errors, such as the misspelling of a variable name or a syntactical error will prevent compilation or whether the software fails to link correctly due to invalid modules. After the software is built, verification tests are run before the software is released for full testing. Verification tests are not intended to be exhaustive and often must be completed within a limited time.
Full testing is intended to be exhaustive and may be very time consuming. For example, full testing may take days or weeks to run. It is advantageous to detect defects as early as possible, e.g., on day 1 rather than day 21 because early defect detection enables developers to start fixing software defects sooner.
Three approaches were previously proposed for addressing the cost of software testing in terms of time, manpower and computing resources. One approach, test elimination involves test selection and minimization to reduce the number of tests that are executed. A second approach referred to as test prioritization schedules tests in a priority order based on coverage of branches and statements of the source code, probability of exposing faults etc. A hybrid approach combines the two previous techniques by starting first with test elimination using source code changes followed by test prioritization to schedule the selected tests.
A number of studies have been conducted to measure the effectiveness of various test selection techniques. These techniques used source code differencing, data flow analysis, and differences in procedure level entities to identify which parts of the software might be affected by the changes. Data flow analysis is difficult in a programming language such as C++ or C which contains pointers, casts, and aliasing. Data flow analysis is not only expensive, it also does not scale to large commercial programs.
As test elimination techniques remove certain tests, their accuracy must be considered. Although some studies show in certain cases that there is no reduction in fault detection, other studies show that fault detection can be severely compromised due to inaccuracies in test elimination. Although test elimination techniques can be guaranteed safe under certain conditions, these conditions do not always occur.
Another major limitation of test elimination techniques is their inability to be effective when a procedure common to all tests is modified. For example, if the “main” procedure of a program is changed in a program written in C language, no tests will be eliminated. This is true because all tests cause the main procedure to be executed. Therefore, changes in the main procedure will require all tests to be rerun.
An improved technique for prioritizing tests, which avoids the problems discussed above, is desirable.